{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Largest Sum in a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthLargestLevelSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中的第 K 大层和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> 和一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>树中的 <strong>层和</strong> 是指 <strong>同一层</strong> 上节点值的总和。</p>\n",
    "\n",
    "<p>返回树中第 <code>k</code> 大的层和（不一定不同）。如果树少于 <code>k</code> 层，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>注意</strong>，如果两个节点与根节点的距离相同，则认为它们在同一层。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/14/binaryytreeedrawio-2.png\" style=\"width: 301px; height: 284px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,8,9,2,1,3,7,4,6], k = 2\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>树中每一层的层和分别是：\n",
    "- Level 1: 5\n",
    "- Level 2: 8 + 9 = 17\n",
    "- Level 3: 2 + 1 + 3 + 7 = 13\n",
    "- Level 4: 4 + 6 = 10\n",
    "第 2 大的层和等于 13 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/14/treedrawio-3.png\" style=\"width: 181px; height: 181px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,null,3], k = 1\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最大的层和是 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数为 <code>n</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-largest-sum-in-a-binary-tree](https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-largest-sum-in-a-binary-tree](https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,8,9,2,1,3,7,4,6]\\n2', '[1,2,null,3]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        g = []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            sm = 0\n",
    "            tmp = []\n",
    "            for x in q:\n",
    "                sm += x.val\n",
    "                if x.left:\n",
    "                    tmp.append(x.left)\n",
    "                if x.right:\n",
    "                    tmp.append(x.right)\n",
    "            g.append(sm)\n",
    "            q = tmp\n",
    "        g = sorted(g, reverse=True)\n",
    "        if len(g) < k:\n",
    "            return -1\n",
    "        return g[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        ans = []\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            total = 0\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                total += node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(total)\n",
    "        ans.sort()\n",
    "        return ans[-k] if len(ans) >= k else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        if not root:\n",
    "            return -1\n",
    "        queue = [root]\n",
    "        ans = []\n",
    "        flag = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            ans_i = []\n",
    "            for i in range(size):\n",
    "                root = queue.pop(0)\n",
    "                ans_i.append(root.val)\n",
    "                if root.left:\n",
    "                    queue.append(root.left)\n",
    "                if root.right:\n",
    "                    queue.append(root.right)\n",
    "            ans.append(sum(ans_i))\n",
    "        ans.sort()\n",
    "        if len(ans) < k:\n",
    "            return -1\n",
    "        print(ans[::-1])\n",
    "        return ans[::-1][k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        #bfs\n",
    "        if not root:\n",
    "            return -1\n",
    "        q = [root]\n",
    "        sm = [] #所有层和\n",
    "        while q:\n",
    "            temp,temp_sm = q,0\n",
    "            q = []\n",
    "            for node in temp:\n",
    "                temp_sm += node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            sm.append(temp_sm)\n",
    "        sm.sort()\n",
    "        return -1 if len(sm) < k else sm[-k]\n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        que = []\n",
    "        que.append(root)\n",
    "        res = []\n",
    "        while len(que) != 0:\n",
    "            length = len(que)\n",
    "            tempSum = 0\n",
    "            for i in range(length):\n",
    "                node = que.pop(0)\n",
    "                tempSum += node.val\n",
    "                if node.left != None:\n",
    "                    que.append(node.left)\n",
    "                if node.right != None:\n",
    "                    que.append(node.right)\n",
    "            res.append(tempSum)\n",
    "        res.sort(reverse=True)\n",
    "        print(len(res))\n",
    "        result = -1 if len(res) < k else res[k-1]\n",
    "        return result\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        res = []\n",
    "        while q:\n",
    "            tmp,s=q,0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s+=node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            res.append(s)\n",
    "        res.sort()\n",
    "        return -1 if len(res)<k else res[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        this_queue=[]\n",
    "        next_queue=[]\n",
    "        if not root:\n",
    "            return\n",
    "        this_queue.append(root)\n",
    "        result = []\n",
    "        while this_queue:\n",
    "            result.append(sum([r.val for r in this_queue]))\n",
    "            for r in this_queue:\n",
    "                if r.left:\n",
    "                    next_queue.append(r.left)\n",
    "                if r.right:\n",
    "                    next_queue.append(r.right)\n",
    "            this_queue=next_queue\n",
    "            next_queue=[]\n",
    "        if k>len(result):\n",
    "            return -1\n",
    "        return sorted(result)[-(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        #bfs\n",
    "        if not root:\n",
    "            return -1\n",
    "        level = 1 #层级\n",
    "        q = [(root,1)]\n",
    "        sm = [] #所有层和\n",
    "        temp_sm = 0 #当前层和\n",
    "        while q:\n",
    "            temp,le = q.pop(0)\n",
    "            if le != level:\n",
    "                level += 1\n",
    "                sm.append(temp_sm)\n",
    "                temp_sm = temp.val\n",
    "            else:\n",
    "                temp_sm += temp.val\n",
    "            if temp.left:\n",
    "                q.append((temp.left,le+1))\n",
    "            if temp.right:\n",
    "                q.append((temp.right,le+1))\n",
    "        sm.append(temp_sm)\n",
    "        sm.sort()\n",
    "        return -1 if len(sm) < k else sm[-k]\n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        # bfs\n",
    "        q = [root]\n",
    "        ans = []\n",
    "        while q:\n",
    "            s = 0\n",
    "            l = []\n",
    "            for node in q:\n",
    "                s += node.val\n",
    "                if node.left:\n",
    "                    l.append(node.left)\n",
    "                if node.right:\n",
    "                    l.append(node.right)\n",
    "            ans.append(s)\n",
    "            q = l\n",
    "        ans.sort()\n",
    "        return -1 if len(ans) < k else ans[-k]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        sums = []\n",
    "        nodes = [root]\n",
    "        while nodes:\n",
    "            sum = 0\n",
    "            for i in range(len(nodes)):\n",
    "                node = nodes.pop(0)\n",
    "                sum += node.val\n",
    "                if node.left:\n",
    "                    nodes.append(node.left)\n",
    "                if node.right:\n",
    "                    nodes.append(node.right)\n",
    "            sums.append(sum)\n",
    "        if k > len(sums):\n",
    "            return -1\n",
    "        sums.sort(reverse=True)\n",
    "        return sums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        sums = []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            s, q2 = 0, []\n",
    "            for x in q:\n",
    "                s += x.val\n",
    "                for y in x.left, x.right:\n",
    "                    if y is not None:\n",
    "                        q2.append(y)\n",
    "            sums.append(s)\n",
    "            q = q2\n",
    "        if len(sums) < k:\n",
    "            return -1\n",
    "        sums.sort(reverse=True)\n",
    "        return sums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        queue = [root]\n",
    "        levsum = []\n",
    "        while queue:\n",
    "            temp = []\n",
    "            tempsum = 0\n",
    "            for i in queue:\n",
    "                tempsum += i.val\n",
    "                if i.left:\n",
    "                    temp.append(i.left)\n",
    "                if i.right:\n",
    "                    temp.append(i.right)\n",
    "            levsum.append(tempsum)\n",
    "            queue = temp\n",
    "        \n",
    "        if k>len(levsum):\n",
    "            return -1\n",
    "        else:\n",
    "            return sorted(levsum)[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        \n",
    "        # 层序遍历\n",
    "\n",
    "        que = deque()\n",
    "        que.append(root)\n",
    "\n",
    "        summ = []\n",
    "\n",
    "        while que:\n",
    "            qlen = len(que)\n",
    "            level_sum = 0\n",
    "\n",
    "            for _ in range(qlen):\n",
    "                node = que.popleft()\n",
    "                val, left, right = (\n",
    "                    node.val, node.left, node.right\n",
    "                )\n",
    "\n",
    "                level_sum += val\n",
    "\n",
    "                if left:\n",
    "                    que.append(left)\n",
    "                \n",
    "                if right:\n",
    "                    que.append(right)\n",
    "\n",
    "            summ.append(level_sum)\n",
    "\n",
    "        if len(summ) < k:\n",
    "            return -1\n",
    "\n",
    "        return sorted(summ, reverse=True)[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        def addNode(nodes, subNode):\n",
    "            if subNode:\n",
    "                nodes.append(subNode)\n",
    "\n",
    "        nodeSums = []\n",
    "        currentlevelNodes = [root]\n",
    "        while currentlevelNodes:\n",
    "            tempNodes = currentlevelNodes.copy()\n",
    "            currentlevelNodes.clear()\n",
    "            nodeSum = 0\n",
    "            for node in tempNodes:\n",
    "                nodeSum += node.val\n",
    "                addNode(currentlevelNodes, node.left)\n",
    "                addNode(currentlevelNodes, node.right)\n",
    "\n",
    "            nodeSums.append(nodeSum)\n",
    "        \n",
    "        if len(nodeSums) < k:\n",
    "            return -1\n",
    "        \n",
    "        nodeSums.sort()\n",
    "        return nodeSums[-k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        sumList = []\n",
    "\n",
    "        q = [root]\n",
    "        while q:\n",
    "            sumList.append(sum(q[i].val for i in range(len(q))))\n",
    "            for _ in range(len(q)):\n",
    "                node = q.pop(0)\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "        sumList.sort()\n",
    "        return -1 if len(sumList) < k else sumList[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        res = []\n",
    "        # ans = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            q = len(queue)\n",
    "            ans = []\n",
    "            for i in range(q):\n",
    "                node = queue.pop(0)\n",
    "                ans.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(sum(ans))\n",
    "        res.sort(reverse=True)\n",
    "        if len(res) < k:\n",
    "            return -1\n",
    "        return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        sumList = []\n",
    "\n",
    "        q = [root]\n",
    "        while q:\n",
    "            sumList.append(0)\n",
    "            # sumList.append(sum(q[i].val for i in range(len(q))))\n",
    "            for _ in range(len(q)):\n",
    "                node = q.pop(0)\n",
    "                sumList[-1] += node.val\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "        sumList.sort()\n",
    "        return -1 if len(sumList) < k else sumList[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def get_lengths(self, root) -> list:\n",
    "        ret_lengths = [ root.val ]\n",
    "        queue = [ root ]\n",
    "        while True:\n",
    "            new_queue = []\n",
    "            cur_level = 0\n",
    "            for item in queue:\n",
    "                if item.left: \n",
    "                    cur_level += item.left.val\n",
    "                    new_queue.append(item.left)\n",
    "                if item.right: \n",
    "                    cur_level += item.right.val\n",
    "                    new_queue.append(item.right)\n",
    "            if new_queue:\n",
    "                ret_lengths.append(cur_level)\n",
    "                # del queue\n",
    "                queue = new_queue\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ret_lengths\n",
    "    \n",
    "    def find_k_large(self, lengths, k):\n",
    "        lengths.sort(reverse=True)\n",
    "        # print(lengths)\n",
    "        return lengths[k - 1]\n",
    "\n",
    "    def kthLargestLevelSum(self, root, k: int) -> int:\n",
    "        lengths = self.get_lengths(root=root)\n",
    "        \n",
    "        if len(lengths) < k: \n",
    "            return -1\n",
    "        \n",
    "        return self.find_k_large(\n",
    "            lengths=lengths,\n",
    "            k=k\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        sum = []\n",
    "        while q:\n",
    "            tmp, s = q, 0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s += node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            sum.append(s)\n",
    "        sum.sort()\n",
    "        return -1 if len(sum) < k else sum[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans = []\n",
    "        queue = [root]\n",
    "        level = 1\n",
    "        while queue:\n",
    "            level_sum = 0\n",
    "            level_size = len(queue)\n",
    "\n",
    "            for _ in range(level_size):\n",
    "                node = queue.pop(0)\n",
    "                level_sum += node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ans.append(level_sum)\n",
    "            level += 1\n",
    "        if level <= k:\n",
    "            return -1\n",
    "        ans.sort(reverse=True)\n",
    "        return ans[k-1] \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        #需要计算每一层的个数来找到第k大的层和。\n",
    "        #使用广度优先遍历记下每一层的个数\n",
    "        \n",
    "        que=list()\n",
    "        que.append(root)\n",
    "        sum=list()\n",
    "        while(len(que)!=0):\n",
    "            q,s=que,0 #这里建立了一个传地址的关系\n",
    "            que=list()\n",
    "            for ql in q:\n",
    "                temp=ql #获取第一个元素\n",
    "                s+=temp.val\n",
    "                if(temp.left):\n",
    "                    que.append(temp.left)\n",
    "                if(temp.right):\n",
    "                    que.append(temp.right)\n",
    "            sum.append(s)\n",
    "        sum.sort() #对sum进行排序\n",
    "        return -1 if len(sum)<k else sum[-k]\n",
    "            \n",
    "                   \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        sum = []\n",
    "        while q:\n",
    "            tmp, s = q, 0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s += node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            sum.append(s)\n",
    "        sum.sort()  # 也可以用快速选择\n",
    "        return -1 if len(sum) < k else sum[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        sum = []\n",
    "        while q:\n",
    "            tmp, s = q, 0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s += node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            sum.append(s)\n",
    "        sum.sort()  # 也可以用快速选择\n",
    "        return -1 if len(sum) < k else sum[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def get_lengths(self, root) -> list:\n",
    "        ret_lengths = [ root.val ]\n",
    "        queue = [ root ]\n",
    "        while queue:\n",
    "            new_queue = []\n",
    "            cur_level = 0\n",
    "            for item in queue:\n",
    "                if item.left: \n",
    "                    cur_level += item.left.val\n",
    "                    new_queue.append(item.left)\n",
    "                if item.right: \n",
    "                    cur_level += item.right.val\n",
    "                    new_queue.append(item.right)\n",
    "            ret_lengths.append(cur_level)\n",
    "            # del queue\n",
    "            queue = new_queue\n",
    "        return ret_lengths\n",
    "    \n",
    "    def find_k_large(self, lengths, k):\n",
    "        lengths.sort(reverse=True)\n",
    "        # print(lengths)\n",
    "        return lengths[k - 1]\n",
    "\n",
    "    def kthLargestLevelSum(self, root, k: int) -> int:\n",
    "        lengths = self.get_lengths(root=root)\n",
    "        \n",
    "        if len(lengths) <= k: \n",
    "            return -1\n",
    "        \n",
    "        return self.find_k_large(\n",
    "            lengths=lengths,\n",
    "            k=k\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        sum = []\n",
    "        while q:\n",
    "            tmp, s = q, 0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s += node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            sum.append(s)\n",
    "        sum.sort()  # 也可以用快速选择\n",
    "        return -1 if len(sum) < k else sum[-k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans = list([root])\n",
    "        ne = list()\n",
    "        res = [root.val]\n",
    "        while ans:\n",
    "            cnt = 0\n",
    "            for i in range(len(ans)):\n",
    "                if ans[i].left:\n",
    "                    ne.append(ans[i].left)\n",
    "                    cnt += ans[i].left.val\n",
    "                if ans[i].right:\n",
    "                    ne.append(ans[i].right)\n",
    "                    cnt += ans[i].right.val\n",
    "            ans = ne.copy()\n",
    "            ne = list()\n",
    "            if cnt != 0:\n",
    "                res.append(cnt)\n",
    "        \n",
    "        res.sort(reverse=True)\n",
    "        # print(res)\n",
    "        if len(res) < k:\n",
    "            return -1\n",
    "        return res[k - 1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        level = [root]\n",
    "        sums = []\n",
    "        while level:\n",
    "            tmp = []\n",
    "            sum = 0\n",
    "            for node in level:\n",
    "                sum += node.val\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "            level = tmp[:]\n",
    "            sums.append(sum)\n",
    "        if len(sums) < k: return -1\n",
    "        return sorted(sums, reverse = True)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        x=[root]\n",
    "        ans=[root.val]\n",
    "        while x:\n",
    "            t=x\n",
    "            x=[]\n",
    "            he=0\n",
    "            for n in t:\n",
    "                if n.left:\n",
    "                    he+=n.left.val\n",
    "                    x.append(n.left)\n",
    "                if n.right:\n",
    "                    he+=n.right.val\n",
    "                    x.append(n.right)\n",
    "            if he:ans.append(he)\n",
    "        if len(ans)<k:\n",
    "            return -1\n",
    "        ans.sort()\n",
    "        return ans[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            level = 0\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                level += node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(level)\n",
    "        if k > len(res):\n",
    "            return -1\n",
    "        res.sort(reverse=True)\n",
    "        return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q=deque([root])\n",
    "        res=[]\n",
    "        while q:\n",
    "            temp=0\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                temp +=node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            res.append(temp)\n",
    "        if len(res)<k:\n",
    "            return -1\n",
    "        return sorted(res)[::-1][k-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root] \n",
    "        ans = [] \n",
    "        while q : \n",
    "            t, s = q, 0 \n",
    "            q = [] \n",
    "            for node in t : \n",
    "                s += node.val \n",
    "                if node.left : q.append(node.left) \n",
    "                if node.right : q.append(node.right) \n",
    "            ans.append(s) \n",
    "        ans.sort() \n",
    "        return -1 if len(ans) < k else ans[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        sum = []\n",
    "        while q:\n",
    "            tmp, s = q, 0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s += node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            sum.append(s)\n",
    "        sum.sort()  # 也可以用快速选择\n",
    "        return -1 if len(sum) < k else sum[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        hq = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            s = 0\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                s += node.val\n",
    "                if node.left : q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            heappush(hq, -s)\n",
    "        for _ in range(k - 1):\n",
    "            if not hq:\n",
    "                break\n",
    "            heappop(hq)\n",
    "        return -1 if not hq else -hq[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "        ans = [root.val]\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            tmp = 0\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()  \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                    tmp += node.left.val\n",
    "                \n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                    tmp += node.right.val\n",
    "            if tmp:\n",
    "                ans.append(tmp)\n",
    "        \n",
    "        if len(ans) < k:\n",
    "            return -1\n",
    "        else:\n",
    "            ans.sort(reverse = True)\n",
    "            return ans[k - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if root is None:\n",
    "            return -1\n",
    "        res = [0]\n",
    "        print(res)\n",
    "        qu = collections.deque([[root,0]])\n",
    "        while qu:\n",
    "            p,lev = qu.popleft()\n",
    "            if lev == len(res)-1:\n",
    "                res[-1] += p.val\n",
    "            else:\n",
    "                res.append(p.val)\n",
    "            if p.left:\n",
    "                qu.append([p.left,lev+1])\n",
    "            if p.right:\n",
    "                qu.append([p.right,lev+1])\n",
    "        #print(res)\n",
    "        res.sort(reverse = True)\n",
    "        #print(res)\n",
    "        if len(res) < k:\n",
    "            return -1\n",
    "        return res[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        sum = []\n",
    "        while q:\n",
    "            tmp, s = q, 0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s += node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            sum.append(s)\n",
    "        sum.sort()  # 也可以用快速选择\n",
    "        return -1 if len(sum) < k else sum[-k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        sum = []\n",
    "        while q:\n",
    "            tmp, s = q, 0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s += node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            sum.append(s)\n",
    "        sum.sort()  # 也可以用快速选择\n",
    "        return -1 if len(sum) < k else sum[-k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        pq = []\n",
    "        q= deque()\n",
    "\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            ans = 0\n",
    "            for i in range(size):\n",
    "                node =q.popleft()\n",
    "                ans += node.val\n",
    "                if node.left : q.append(node.left) \n",
    "                if node.right: q.append(node.right)\n",
    "            heapq.heappush(pq,ans)\n",
    "            if len(pq)>k:\n",
    "                heapq.heappop(pq)\n",
    "\n",
    "        return heapq.heappop(pq) if len(pq)==k else -1        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        def addNode(nodes, subNode):\n",
    "            if subNode:\n",
    "                nodes.append(subNode)\n",
    "\n",
    "        nodeSums = [root.val]\n",
    "        currentlevelNodes = [root]\n",
    "        while currentlevelNodes:\n",
    "            tempNodes = currentlevelNodes.copy()\n",
    "            currentlevelNodes.clear()\n",
    "            for node in tempNodes:\n",
    "                addNode(currentlevelNodes, node.left)\n",
    "                addNode(currentlevelNodes, node.right)\n",
    "            nodeSum = 0\n",
    "            for node in currentlevelNodes:\n",
    "                nodeSum += node.val\n",
    "            if nodeSum > 0:\n",
    "                nodeSums.append(nodeSum)\n",
    "        \n",
    "        if len(nodeSums) < k:\n",
    "            return -1\n",
    "        \n",
    "        nodeSums.sort()\n",
    "        return nodeSums[-k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        level=1\n",
    "        ans=0\n",
    "        if not root:\n",
    "            return -1\n",
    "        stack=[]\n",
    "        stack.append(root)\n",
    "        nexstack=[]\n",
    "        ans=[]\n",
    "        v=0\n",
    "        while stack:\n",
    "            cur =stack.pop(0)\n",
    "            v=v+cur.val\n",
    "            if cur.left:\n",
    "                nexstack.append(cur.left)\n",
    "            if cur.right:\n",
    "                nexstack.append(cur.right)\n",
    "            if stack==[]:\n",
    "                ans.append(v)\n",
    "                v=0\n",
    "            if stack==[] and nexstack:\n",
    "                level=level+1\n",
    "                stack=nexstack\n",
    "                nexstack=[]\n",
    " \n",
    "        ans.sort(reverse=True)\n",
    "        if len(ans)<k:\n",
    "            return -1\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        layer_sum_lst, node_lst = [], [root]\n",
    "        while node_lst:\n",
    "            sum_value, tmp_lst = 0, []\n",
    "            for node in node_lst:\n",
    "                sum_value += node.val\n",
    "                if node.left:\n",
    "                    tmp_lst.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp_lst.append(node.right)\n",
    "            layer_sum_lst.append(sum_value)\n",
    "            node_lst = tmp_lst[:]\n",
    "        layer_sum_lst = sorted(layer_sum_lst, reverse=True)\n",
    "        if k > len(layer_sum_lst):\n",
    "            return -1\n",
    "        return layer_sum_lst[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        res = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            s = 0\n",
    "            for _ in range(n):\n",
    "                cur = q.popleft()\n",
    "                s += cur.val\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            res.append(s)\n",
    "        res.sort()\n",
    "        return res[-k] if len(res) >= k else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        ans = []\n",
    "        while q:\n",
    "            temp = q\n",
    "            q = []\n",
    "            sub_sum = 0\n",
    "            for node in temp:\n",
    "                sub_sum += node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(sub_sum)\n",
    "        ans.sort()\n",
    "        ans.reverse()\n",
    "        if k>len(ans):\n",
    "            return -1\n",
    "        else:\n",
    "            return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        sum = []\n",
    "        while q:\n",
    "            tmp, s = q, 0\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                s += node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            sum.append(s)\n",
    "        sum.sort()  # 也可以用快速选择\n",
    "        return -1 if len(sum) < k else sum[-k]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        mapping = []\n",
    "        que = deque()\n",
    "        que.append([root,0])\n",
    "        while(que):\n",
    "            node, depth = que.popleft()\n",
    "            if(depth == len(mapping)):\n",
    "                mapping.append(0)\n",
    "            mapping[depth] += node.val\n",
    "            if(node.left):\n",
    "                que.append([node.left,depth+1])\n",
    "            if(node.right):\n",
    "                que.append([node.right,depth+1])\n",
    "        if(k > len(mapping)):\n",
    "            return -1\n",
    "        return sorted(mapping,key=lambda x:-x)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def quickSelect(self,nums,left,right,k):\n",
    "        pivotId = random.randint(left, right)\n",
    "        nums[pivotId],nums[right] = nums[right],nums[pivotId]\n",
    "\n",
    "        idx = left\n",
    "        tag = left\n",
    "        while idx < right:\n",
    "            if nums[idx] > nums[right]:\n",
    "                nums[tag],nums[idx] = nums[idx],nums[tag]\n",
    "                tag+=1\n",
    "            idx+=1\n",
    "        nums[tag],nums[right] = nums[right],nums[tag]\n",
    "        if tag == k:return nums[k]\n",
    "        if tag > k:return self.quickSelect(nums,left,tag-1,k)\n",
    "        if tag < k:return self.quickSelect(nums, tag+1,right,k)\n",
    "\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        sumList = []\n",
    "\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            sumList.append(0)\n",
    "            # sumList.append(sum(q[i].val for i in range(len(q))))\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                sumList[-1] += node.val\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "        \n",
    "        if len(sumList) < k:return -1\n",
    "        sumList.sort()\n",
    "        return sumList[-k]\n",
    "        # self.quickSelect(sumList, 0, (len(sumList)-1), k-1)\n",
    "        # return sumList[k-1]\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            res.append([x.val for x in queue])\n",
    "            ll = []\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    ll.append(node.left)\n",
    "                if node.right:\n",
    "                    ll.append(node.right)\n",
    "            queue = ll\n",
    "        ans = []\n",
    "        for r in res:\n",
    "            ans.append(sum(r))\n",
    "        ans.sort()\n",
    "        return -1 if len(ans) < k else ans[-k]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        dq = deque()\n",
    "        dq.append(root)\n",
    "        total = []\n",
    "        while dq:\n",
    "            s = 0\n",
    "            sze = len(dq)\n",
    "            for _ in range(sze):\n",
    "                node = dq.popleft()\n",
    "                s += node.val\n",
    "                if node.left:\n",
    "                    dq.append(node.left)\n",
    "                if node.right:\n",
    "                    dq.append(node.right)\n",
    "            total.append(s)\n",
    "        total.sort(reverse=True)\n",
    "        return total[k - 1] if len(total) >= k else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        #bfs\n",
    "        if not root:\n",
    "            return -1\n",
    "        level = 1 #层级\n",
    "        q = [(root,1)]\n",
    "        sm = [] #所有层和\n",
    "        temp_sm = 0 #当前层和\n",
    "        while q:\n",
    "            temp,le = q.pop(0)\n",
    "            if le != level:\n",
    "                level += 1\n",
    "                sm.append(temp_sm)\n",
    "                temp_sm = temp.val\n",
    "            else:\n",
    "                temp_sm += temp.val\n",
    "            if temp.left:\n",
    "                q.append((temp.left,le+1))\n",
    "            if temp.right:\n",
    "                q.append((temp.right,le+1))\n",
    "        sm.append(temp_sm)\n",
    "        sm.sort()\n",
    "        return -1 if len(sm) < k else sm[-k]\n",
    "        # if k > len(sm): return -1\n",
    "        # sm = sorted(sm, reverse=True)\n",
    "        # _k = 0\n",
    "        # temp =-1\n",
    "        # for l in sm:\n",
    "        #     if l != temp:\n",
    "        #         temp = l\n",
    "        #         _k += 1\n",
    "        #     if _k == k:\n",
    "        #         return l\n",
    "        # return -1\n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        nodes = [(root,0)]\n",
    "        sums = []\n",
    "        childs = []\n",
    "        cur_layer = 0\n",
    "        cur_sum = 0\n",
    "        while len(nodes)>0:\n",
    "            node,layer = nodes.pop(0)\n",
    "            if layer == cur_layer:\n",
    "                cur_sum += node.val\n",
    "            else:\n",
    "                sums.append(cur_sum)\n",
    "                cur_layer = layer\n",
    "                cur_sum = node.val\n",
    "            if node.left:\n",
    "                nodes.append([node.left,layer+1])\n",
    "            if node.right:\n",
    "                nodes.append([node.right,layer+1])\n",
    "        sums.append(cur_sum)\n",
    "        sums = sorted(sums)\n",
    "        if len(sums)<k:\n",
    "            return -1\n",
    "        return sums[-k]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        stack = [root]\n",
    "        res = []\n",
    "\n",
    "        while stack:\n",
    "            level_val = 0\n",
    "            for i in range(len(stack)):\n",
    "                node = stack.pop(0)\n",
    "                level_val += node.val\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                \n",
    "            res.append(level_val)\n",
    "        res = sorted(res)\n",
    "        print(res)\n",
    "        return res[-k] if len(res) >= k else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        level=1\n",
    "        ans=0\n",
    "        if not root:\n",
    "            return -1\n",
    "        stack=[]\n",
    "        stack.append(root)\n",
    "        nexstack=[]\n",
    "        ans=[]\n",
    "        v=0\n",
    "        while stack:\n",
    "            cur =stack.pop()\n",
    "            v=v+cur.val\n",
    "            if cur.left:\n",
    "                nexstack.append(cur.left)\n",
    "            if cur.right:\n",
    "                nexstack.append(cur.right)\n",
    "            if stack==[]:\n",
    "                ans.append(v)\n",
    "                v=0\n",
    "            if stack==[] and nexstack:\n",
    "                level=level+1\n",
    "                stack=nexstack\n",
    "                nexstack=[]\n",
    " \n",
    "        ans.sort(reverse=True)\n",
    "        if len(ans)<k:\n",
    "            return -1\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def k_select(self, level_sums, k):\n",
    "        if len(level_sums) == 1:\n",
    "            return level_sums[0]\n",
    "        n = len(level_sums)\n",
    "        mid = n // 2\n",
    "        pivot = level_sums[mid]\n",
    "        less = []\n",
    "        equal = []\n",
    "        more = []\n",
    "        for level_sum in level_sums:\n",
    "            if level_sum < pivot:\n",
    "                less.append(level_sum)\n",
    "            elif level_sum > pivot:\n",
    "                more.append(level_sum)\n",
    "            else:\n",
    "                equal.append(level_sum)\n",
    "        if len(more) >= k:\n",
    "            return self.k_select(more, k)\n",
    "        elif k > len(more) + len(equal):\n",
    "            return self.k_select(less, k - (len(more) + len(equal)))\n",
    "        else:\n",
    "            return pivot\n",
    "\n",
    "    def bfs(self, root):\n",
    "        level_sums = []\n",
    "        queue = collections.deque([])\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            cur_sum = 0\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                cur_sum += node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            level_sums.append(cur_sum)\n",
    "        return level_sums\n",
    "\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        level_sums = self.bfs(root)\n",
    "        if len(level_sums) < k:\n",
    "            return -1\n",
    "        return self.k_select(level_sums, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def partition(self, level_sum:List[int], left:int, right:int, pivot:int):\n",
    "        x=level_sum[pivot]\n",
    "        level_sum[pivot], level_sum[right]=level_sum[right], level_sum[pivot]\n",
    "        store_idx=left\n",
    "        for i in range(left, right):\n",
    "            if level_sum[i]>x:\n",
    "                level_sum[i], level_sum[store_idx]=level_sum[store_idx], level_sum[i]\n",
    "                store_idx+=1\n",
    "        level_sum[store_idx], level_sum[right]=level_sum[right], level_sum[store_idx]\n",
    "        return store_idx\n",
    "\n",
    "    def quickSort(self, level_sum:List[int], left:int, right:int, k:int):\n",
    "        pivot=random.randint(left, right)\n",
    "        t=self.partition(level_sum, left, right, pivot)\n",
    "        if t==k:\n",
    "            return level_sum[t]\n",
    "        if t<k:\n",
    "            return self.quickSort(level_sum, t+1, right, k)\n",
    "        return self.quickSort(level_sum, left, t-1, k)\n",
    "\n",
    "\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        level_sum=[]\n",
    "        def bfs():\n",
    "            q=[root]\n",
    "            while q:\n",
    "                size=len(q)\n",
    "                s=0\n",
    "                for _ in range(size):\n",
    "                   t=q.pop(0)\n",
    "                   s+=t.val\n",
    "                   if t.left:\n",
    "                       q.append(t.left)\n",
    "                   if t.right:\n",
    "                       q.append(t.right)\n",
    "                level_sum.append(s)\n",
    "        bfs()\n",
    "        n=len(level_sum)\n",
    "        if n<k:\n",
    "            return -1\n",
    "        return self.quickSort(level_sum, 0, n-1, k-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ls=[]\n",
    "        if not root :\n",
    "            return -1\n",
    "        q=collections.deque()\n",
    "        q.append(root)\n",
    "        kk=0\n",
    "        ans=[]\n",
    "        while q:\n",
    "            lenq=len(q)\n",
    "            #print(lenq,\"------\")\n",
    "            adds=0\n",
    "            for i in range(lenq):\n",
    "                tp=q.popleft()\n",
    "                #print(tp.val)\n",
    "                adds+=tp.val\n",
    "                if tp.left:\n",
    "                    q.append(tp.left)\n",
    "                if tp.right:\n",
    "                    q.append(tp.right)\n",
    "            ans.append(adds)\n",
    "            kk+=1\n",
    "        ans.sort()\n",
    "        #print(ans)\n",
    "        if k>len(ans):\n",
    "            return -1\n",
    "        return ans[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        pq = []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            cnt = 0\n",
    "            for _  in range(size):\n",
    "                cur = queue.popleft()\n",
    "                cnt += cur.val\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "            heapq.heappush(pq, cnt)\n",
    "            if len(pq) > k:\n",
    "                heapq.heappop(pq)\n",
    "        if len(pq) < k:\n",
    "            return -1\n",
    "        else:\n",
    "            return pq[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        mapping = []\n",
    "        que = deque()\n",
    "        que.append([root,0])\n",
    "        while(que):\n",
    "            node, depth = que.popleft()\n",
    "            if(depth == len(mapping)):\n",
    "                mapping.append(0)\n",
    "            mapping[depth] += node.val\n",
    "            if(node.left):\n",
    "                que.append([node.left,depth+1])\n",
    "            if(node.right):\n",
    "                que.append([node.right,depth+1])\n",
    "        if(k > len(mapping)):\n",
    "            return -1\n",
    "        return sorted(mapping,key=lambda x:-x)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = collections.deque([root])\n",
    "        stack = []\n",
    "        while q:\n",
    "            l = []\n",
    "            stack.append(sum([node.val for node in q]))\n",
    "            for node in q:\n",
    "                if node.left:\n",
    "                    l.append(node.left)\n",
    "                if node.right:\n",
    "                    l.append(node.right)\n",
    "            q = l\n",
    "        print(stack)\n",
    "        stack.sort()\n",
    "        print(stack)\n",
    "        if len(stack)<k:\n",
    "            return -1\n",
    "        return stack[-k]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        level=1\n",
    "        ans=0\n",
    "        if not root:\n",
    "            return -1\n",
    "        stack=[]\n",
    "        stack.append(root)\n",
    "        nexstack=[]\n",
    "        ans=[]\n",
    "        v=0\n",
    "        while stack:\n",
    "            cur =stack.pop(0)\n",
    "            v=v+cur.val\n",
    "            if cur.left:\n",
    "                nexstack.append(cur.left)\n",
    "            if cur.right:\n",
    "                nexstack.append(cur.right)\n",
    "            if stack==[]:\n",
    "                ans.append(v)\n",
    "                v=0\n",
    "            if stack==[] and nexstack:\n",
    "                level=level+1\n",
    "                stack=nexstack\n",
    "                nexstack=[]\n",
    " \n",
    "        ans.sort(reverse=True)\n",
    "        print(ans)\n",
    "        if len(ans)<k:\n",
    "            return -1\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        sl = SortedList()\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            ans = 0\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                ans += node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            sl.add(ans)\n",
    "        n = len(sl)\n",
    "        return sl[-k] if k <= n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import *\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        p = deque()\n",
    "        p.append(root)\n",
    "        re_sum = []\n",
    "        while p:\n",
    "            tmp = p\n",
    "            p = deque()\n",
    "            sum_ = 0\n",
    "            for i in tmp:\n",
    "                sum_ += i.val\n",
    "                if i.left:\n",
    "                   p.append(i.left)\n",
    "                if i.right:\n",
    "                    p.append(i.right)\n",
    "            re_sum.append(sum_)\n",
    "        re_sum = sorted(re_sum)\n",
    "        print(re_sum)\n",
    "        if k > len(re_sum):\n",
    "            return -1\n",
    "        else:\n",
    "            return re_sum[-k]\n",
    "        \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        every_sum = []\n",
    "        def dfs(node,level):\n",
    "            if not node:\n",
    "                return\n",
    "            if level<len(every_sum):\n",
    "                every_sum[level]+=node.val\n",
    "            else:\n",
    "                every_sum.append(node.val)\n",
    "            dfs(node.left,level+1)\n",
    "            dfs(node.right,level+1)\n",
    "\n",
    "        dfs(root,0)\n",
    "        every_sum.sort(reverse=True)\n",
    "        if len(every_sum)<k:\n",
    "            return -1\n",
    "        return every_sum[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        res = []\n",
    "\n",
    "        def dfs(root, i):\n",
    "            if not root:\n",
    "                return\n",
    "            if i > len(res):\n",
    "                res.append(0)\n",
    "            res[i - 1] += root.val\n",
    "            dfs(root.left, i + 1)\n",
    "            dfs(root.right, i + 1)\n",
    "        \n",
    "        dfs(root, 1)\n",
    "        return sorted(res, reverse=True)[k - 1] if k <= len(res) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans=[]\n",
    "        def dfs(root,lev):\n",
    "            if not root:\n",
    "                return \n",
    "            if len(ans)<=lev:\n",
    "                ans.append(0)\n",
    "            ans[lev]+=root.val\n",
    "            dfs(root.left,lev+1)\n",
    "            dfs(root.right,lev+1)\n",
    "        dfs(root,0)\n",
    "        ans.sort(reverse=True)\n",
    "\n",
    "        return ans[k-1] if 0<=k-1<len(ans) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        层和列表 = [0]\n",
    "        def 遍历(root, x):\n",
    "            if root:\n",
    "                if len(层和列表) == x:\n",
    "                    层和列表.append(0)\n",
    "                层和列表[x] += root.val\n",
    "                遍历(root.left, x+1)\n",
    "                遍历(root.right, x+1)\n",
    "        遍历(root, 0)\n",
    "        if len(层和列表) < k:\n",
    "            return -1\n",
    "        层和列表.sort()\n",
    "        return 层和列表[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        层和列表 = [0]\n",
    "        def 遍历(root, x):\n",
    "            if root:\n",
    "                if len(层和列表) == x:\n",
    "                    层和列表.append(0)\n",
    "                层和列表[x] += root.val\n",
    "                遍历(root.left, x+1)\n",
    "                遍历(root.right, x+1)\n",
    "        遍历(root, 0)\n",
    "        if len(层和列表) < k:\n",
    "            return -1\n",
    "        层和列表.sort()\n",
    "        print(层和列表)\n",
    "        return 层和列表[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        # que = []\n",
    "        # que.append(root)\n",
    "        # res = []\n",
    "        # while len(que) != 0:\n",
    "        #     length = len(que)\n",
    "        #     tempSum = 0\n",
    "        #     for i in range(length):\n",
    "        #         node = que.pop(0)\n",
    "        #         tempSum += node.val\n",
    "        #         if node.left != None:\n",
    "        #             que.append(node.left)\n",
    "        #         if node.right != None:\n",
    "        #             que.append(node.right)\n",
    "        #     res.append(tempSum)\n",
    "        # res.sort(reverse=True)\n",
    "        # print(len(res))\n",
    "        # result = -1 if len(res) < k else res[k-1]\n",
    "        # return result\n",
    "\n",
    "        vec = []\n",
    "        def dfs(root, level):\n",
    "            if root == None:\n",
    "                return \n",
    "            if len(vec) <= level:\n",
    "                vec.append(0)\n",
    "            vec[level] += root.val\n",
    "            dfs(root.left, level + 1)\n",
    "            dfs(root.right, level + 1)\n",
    "        dfs(root, 0)\n",
    "        if len(vec) < k:\n",
    "            return -1\n",
    "        else:\n",
    "            vec.sort(reverse=True)\n",
    "            return vec[k-1]\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        层和列表 = [0]\n",
    "        def 遍历(root, x):\n",
    "            if root:\n",
    "                if len(层和列表) == x:\n",
    "                    层和列表.append(0)\n",
    "                层和列表[x] += root.val\n",
    "                遍历(root.left, x+1)\n",
    "                遍历(root.right, x+1)\n",
    "        遍历(root, 0)\n",
    "        if len(层和列表) < k:\n",
    "            return -1\n",
    "        层和列表.sort()\n",
    "        print(层和列表)\n",
    "        return 层和列表[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans=[]\n",
    "        def dfs(root,lev):\n",
    "            if not root:\n",
    "                return \n",
    "            if len(ans)<=lev:\n",
    "                ans.append(0)\n",
    "            ans[lev]+=root.val\n",
    "            dfs(root.left,lev+1)\n",
    "            dfs(root.right,lev+1)\n",
    "        dfs(root,0)\n",
    "        ans.sort(reverse=True)\n",
    "\n",
    "        return ans[k-1] if 0<=k-1<len(ans) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans=[]\n",
    "        def dfs(root,lev):\n",
    "            if not root:\n",
    "                return \n",
    "            if len(ans)<=lev:\n",
    "                ans.append(0)\n",
    "            ans[lev]+=root.val\n",
    "            dfs(root.left,lev+1)\n",
    "            dfs(root.right,lev+1)\n",
    "        dfs(root,0)\n",
    "        ans.sort(reverse=True)\n",
    "\n",
    "        return ans[k-1] if 0<=k-1<len(ans) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans=[]\n",
    "        def dfs(root,lev):\n",
    "            if not root:\n",
    "                return \n",
    "            if len(ans)<=lev:\n",
    "                ans.append(0)\n",
    "            ans[lev]+=root.val\n",
    "            dfs(root.left,lev+1)\n",
    "            dfs(root.right,lev+1)\n",
    "        dfs(root,0)\n",
    "        ans.sort(reverse=True)\n",
    "\n",
    "        return ans[k-1] if 0<=k-1<len(ans) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans=[0]*100000\n",
    "        def dfs(root,lev):\n",
    "            if not root:\n",
    "                return \n",
    "            ans[lev]+=root.val\n",
    "            dfs(root.left,lev+1)\n",
    "            dfs(root.right,lev+1)\n",
    "        dfs(root,0)\n",
    "        ans.sort(reverse=True)\n",
    "\n",
    "        return ans[k-1] if ans[k-1]!=0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans=[0]*100000\n",
    "        def dfs(root,lev):\n",
    "            if not root:\n",
    "                return \n",
    "            ans[lev]+=root.val\n",
    "            dfs(root.left,lev+1)\n",
    "            dfs(root.right,lev+1)\n",
    "        dfs(root,0)\n",
    "        ans.sort(reverse=True)\n",
    "\n",
    "        return ans[k-1] if ans[k-1]!=0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        def bfs(root, depth):\n",
    "            if root == None:\n",
    "                return\n",
    "            if depth not in self.nums:\n",
    "                self.nums[depth] = root.val\n",
    "            else:\n",
    "                self.nums[depth] += root.val\n",
    "            bfs(root.left, depth+1)\n",
    "            bfs(root.right, depth+1)\n",
    "        self.nums = {}\n",
    "        bfs(root, 0)\n",
    "        if k > len(self.nums):\n",
    "            return -1\n",
    "        return sorted(self.nums.values(),reverse=True)[k-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        else:\n",
    "            self.Dict = {1:root.val}\n",
    "        if root.left:\n",
    "            self.myseek(root.left,2)\n",
    "        if root.right:\n",
    "            self.myseek(root.right,2)\n",
    "        res = []\n",
    "        for i in self.Dict:\n",
    "            res.append([i,self.Dict[i]])\n",
    "        res.sort(key = lambda x:-x[1])\n",
    "        #print(res)\n",
    "        return res[k-1][1] if len(res)>=k else -1\n",
    "        #print(res)\n",
    "    def myseek(self,root,degree):\n",
    "        if degree not in self.Dict:\n",
    "            self.Dict[degree] = root.val\n",
    "        else:\n",
    "            self.Dict[degree] += root.val\n",
    "        if root.left:\n",
    "            a = degree\n",
    "            self.myseek(root.left,a+1)\n",
    "        if root.right:\n",
    "            a = degree\n",
    "            self.myseek(root.right,a+1)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        c = Counter()\n",
    "        def dfs(node, depth=0):\n",
    "            c[depth] += node.val\n",
    "            if node.left:\n",
    "                dfs(node.left, depth + 1)\n",
    "            if node.right:\n",
    "                dfs(node.right, depth + 1)\n",
    "        dfs(root)\n",
    "        if len(c) < k:\n",
    "            return -1\n",
    "        l = sorted(c.values(), reverse=True)\n",
    "        return l[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        c = Counter()\n",
    "        def dfs(node, depth=0):\n",
    "            c[depth] += node.val\n",
    "            if node.left:\n",
    "                dfs(node.left, depth + 1)\n",
    "            if node.right:\n",
    "                dfs(node.right, depth + 1)\n",
    "        dfs(root)\n",
    "        if len(c) < k:\n",
    "            return -1\n",
    "        return sorted(c.values(), reverse=True)[k-1]\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
